package edu.dayu.demo1;

import java.util.HashSet;

/**
 *  给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。
 *  输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
 * 输出: 16
 * 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
 * 思路：怎么判断两个单词不包含相同字符？ 字典树？似乎不太行，这个题目不需要顺序。
 *          用set？ 将两个字符串的所有字符丢进去。如果个数等于两个字符的就ok。时间复杂度 O（n^3）好像也不太行
 * 思路2：采用位运算，把每个单词都换成一个二进制数，也就是单词表 26位，这个二进制数也是 26，只要每一位上是 1，
 *       那么说明这个单词存在这个字母，然后两个数字进行与运算，为0说明没有相同的字符。
 *       难点在于怎么计算每个单词的二进制数 我们 用每个单词的字符减去 a ，这样就得到了这个字符的位置
 *       然后让1往右 移动它的位置长度，然后与前面计算的数进行或运算，这个位置不同或者相同都为1.
 *       时间复杂度 O（2*n^2），代码整洁度高很多，时间复杂度也低一些。
 */
public class 单词长度的最大乘积 {
    public static void main(String[] args) {
        String[] words = {"eae","ea","aaf","bda","fcf","dc","ac","ce","cefde","dabae"};
//        System.out.println(maxProduct(words));
        System.out.println(position(words));

    }

    /**
     * 思路1 ： 利用 set 来处理单词重复的问题
     * @param words
     * @return
     */
    public static int maxProduct(String[] words) {
        int sum =0;
        for (int i = 0; i < words.length-1; i++) {
            for (int j = i+1; j < words.length ; j++) {
                if (repeat(words[i],words[j])){
                    int temp = words[i].length()*words[j].length();
                    if (temp>sum)
                        sum=temp;
                }
            }
        }
        return sum;
    }

    public static boolean repeat(String a,String b){
        HashSet<Character> set1 = new HashSet<Character>();
        HashSet<Character> set2 = new HashSet<Character>();
        HashSet<Character> set3 = new HashSet<Character>();
        char[] chars = a.toCharArray();
        char[] chars1 = b.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            set1.add(chars[i]);
            set3.add(chars[i]);
        }
        for (int i = 0; i < chars1.length; i++) {
            set2.add(chars1[i]);
            set3.add(chars1[i]);
        }
        if (set1.size()+set2.size()==set3.size())
            return true;
        else
            return false;
    }

    /**
     * 采用位运算，把每个单词都换成一个二进制数，也就是单词表 26位，这个二进制数也是 26，只要每一位上是 1，
     * 那么说明这个单词存在这个字母，然后两个数字进行与运算，为0说明没有相同的字符。
     * 难点在于怎么计算每个单词的二进制数 我们 用每个单词的字符减去 a ，这样就得到了这个字符的位置
     *              然后让1往右 移动它的位置长度，然后与前面计算的数进行或运算，这个位置不同或者相同都为1.
     * @param words
     * @return
     */
    public static int position(String[] words){
        int sum = 0;
        int[] m = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int mask = 0;
            String str = words[i];
            for (int j =0;j<str.length();j++){
                mask|=1<<((str.charAt(j)-'a'));
            }
            m[i] = mask;
        }
        for (int i = 0; i < words.length; i++) {
            for (int j = 0;j<i;j++){
                if ((m[i]&m[j]) == 0){
                    int cur = words[i].length()*words[j].length();
                    if (cur>sum)
                        sum = cur;
                }
            }
        }
        return sum;
    }
}
